package leetcode.weekly.week328;

import java.util.HashMap;
import java.util.Map;

//Solution3Test
public class Solution3 {

	public long countGood(int[] nums, int k) {
		long ans = 0;
		int l = 0, r = 0, len = nums.length;
		Map<Integer, Integer> cnt = new HashMap<>();
		int has = 0;
		while (l <= r && l < len) {
			while (has < k && r < len) {
				int add = nums[r];
				int e = cnt.getOrDefault(add, 0);
				has += e;
				cnt.put(add, e + 1);
				r++;
			}
			if (has >= k) {
				ans += len - r + 1;
			}
			int sub = nums[l];
			cnt.put(sub, cnt.get(sub) - 1);
			has -= cnt.get(sub);
			l++;
		}
		return ans;
	}
}
